Search for: All records

In recent years, achieving verifiable quantum advantage on a NISQ device has emerged as an important open problem in quantum information. The sampling-based quantum advantages are not known to have efficient verification methods. This article investigates the verification of quantum advantage from a cryptographic perspective. We establish a strong connection between the verifiability of quantum advantage and cryptographic and complexity primitives, including efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states (EFI), pseudorandom states (PRS), and variants of minimum circuit size problems (MCSP). Specifically, we prove that a) a sampling-based quantum advantage is either verifiable or can be used to buildEFIand evenPRSand b) polynomial-time algorithms for a variant ofMCSPwould imply efficient verification of quantum advantages. Our work shows that the quest for verifiable quantum advantages may lead to applications of quantum cryptography, and the construction of quantum primitives can provide new insights into the verifiability of quantum advantages. 

QAC0 is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by Moore as a quantum counterpart of AC0, along with the conjecture that QAC0 circuits cannot compute PARITY. In this work, we make progress on this long-standing conjecture: we show that any depth-𝑑 QAC0 circuit requires 𝑛^{1+3^{−𝑑}} ancillae to compute a function with approximate degree Θ(𝑛), which includes PARITY, MAJORITY and MOD_𝑘. We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first lower bound on the super-linear sized QAC0. Regarding PARITY, we show that any further improvement on the size of ancillae to 𝑛^{1+exp(−𝑜(𝑑))} would imply that PARITY ∉ QAC0. These lower bounds are derived by giving low-degree approximations to QAC0 circuits. We show that a depth-𝑑 QAC0 circuit with 𝑎 ancillae, when applied to low-degree operators, has a degree (𝑛 + 𝑎)^{1−3^{−𝑑}} polynomial approximation in the spectral norm. This implies that the class QLC0, corresponding to linear size QAC0 circuits, has an approximate degree 𝑜(𝑛). This is a quantum generalization of the result that LC0 circuits have an approximate degree 𝑜(𝑛) by Bun, Kothari, and Thaler. Our result also implies that QLC0 ≠ NC1. 

The class MIP^* of quantum multiprover interactive proof systems with entanglement is much more powerful than its classical counterpart MIP [Babai et al., 1991; Zhengfeng Ji et al., 2020; Zhengfeng Ji et al., 2020]: while MIP = NEXP, the quantum class MIP^* is equal to RE, a class including the halting problem. This is because the provers in MIP^* can share unbounded quantum entanglement. However, recent works [Qin and Yao, 2021; Qin and Yao, 2023] have shown that this advantage is significantly reduced if the provers' shared state contains noise. This paper attempts to exactly characterize the effect of noise on the computational power of quantum multiprover interactive proof systems. We investigate the quantum two-prover one-round interactive system MIP^*[poly,O(1)], where the verifier sends polynomially many bits to the provers and the provers send back constantly many bits. We show noise completely destroys the computational advantage given by shared entanglement in this model. Specifically, we show that if the provers are allowed to share arbitrarily many EPR states, where each EPR state is affected by an arbitrarily small constant amount of noise, the resulting complexity class is equivalent to NEXP = MIP. This improves significantly on the previous best-known bound of NEEEXP (nondeterministic triply exponential time) [Qin and Yao, 2021]. We also show that this collapse in power is due to the noise, rather than the O(1) answer size, by showing that allowing for noiseless EPR states gives the class the full power of RE = MIP^*[poly, poly]. Along the way, we develop two technical tools of independent interest. First, we give a new, deterministic tester for the positivity of an exponentially large matrix, provided it has a low-degree Fourier decomposition in terms of Pauli matrices. Secondly, we develop a new invariance principle for smooth matrix functions having bounded third-order Fréchet derivatives or which are Lipschitz continuous.